When data is to be stored or transmitted, it is usually converted to this end into an alternative, compressed representation.
One of the most powerful tools in the field of data compression is vector quantization, which is applied to data in vector format. Basic vector quantization makes use of a codebook, which associates a number of code vectors to a respective codebook index. For each input data vector, one of the code vectors is determined to be the best representation of the input data vector. The determined code vector constitutes thus a quantized data vector. The codebook index that is associated to this code vector is selected as a compressed representation of the input data vector. In decoding, a decompressed quantized data vector can then be regained by replicating the code vector corresponding to the code index.
Alternatively to the basic vector quantization, also an advanced vector quantization, like multistage vector quantization or predictive vector quantization, can be used for the data compression, in order to enhance the accuracy of the quantization.
In multistage vector quantization, the input data vector is quantized in two or more additive stages. The objective is to find a code vector combination, in other words a sum of code vectors selected at different stages, that minimizes the distortion which results in the quantization. Each of the selected code vectors is then mapped to a codebook index in a respective codebook. The code vector selections are performed based on a search algorithm. The simplest approach is to use a sequential search. In this case, a first code vector is determined at a first stage. The difference between the input data vector and the first code vector is used as input vector for a second stage, etc. A more sophisticated approach is, for example, the use of a tree search algorithm that performs the code vector selections at different stages in a joint manner. In an M-L search tree vector quantization, for instance, the M best first code vectors are determined at the first stage. Proceeding from these M best first code vectors, the M best second code vectors are determined at the second stage, etc. Finally, the best combination of the M best first to L code vectors is selected. The sequential search approach and the M-L search tree approach was described for instance by J. Nurminen in: “Pitch-cycle waveform quantization in a 4.0 kbps WI speech coder”, Master of Science thesis, Tampere University of Technology, Department of Information Technology, 2001.
In predictive vector quantization, a prediction of the input data vector is calculated using information about a finite number of previously quantized vectors. Then, the prediction error vector, which is also referred to as prediction residual, is quantized instead of the original input vector by selecting a code vector. Again, the selected code vector is compressed by mapping it to a codebook index. In decoding, the output is computed by adding a calculated prediction and the regained quantized prediction error vector. The predictive vector quantization was equally described for instance in the above cited document “Pitch-cycle waveform quantization in a 4.0 kbps WI speech coder”.
The codebook indices that are determined in the vector quantization can be stored and/or transmitted as such. Alternatively, the coding can be further enhanced by applying some lossless compression technique, like the well-known Huffman coding approach, to compress the codebook indices. However, simply applying a lossless compression technique does usually not result in considerable improvements. Such techniques are efficient, in case the probabilities with which different codebook indices are selected are quite different from each other. Often, though, the probabilities for the selection of different codebook indices are quite similar, making lossless coding relatively inefficient.
The basic dynamic codebook reordering technique was designed to enhance the situation by making the probability distribution more favourable from the viewpoint of lossless compression. The main idea of dynamic codebook reordering is to reorder the codebook in such a way that the selected code vector becomes the first code vector and that the remaining code vectors are arranged according to their distance to this first vector. Since the data that is to be compressed is usually not completely uncorrelated, this makes the probability distribution non-flat, which in turn reduces the entropy and makes the codebook indices easier to compress. Dynamic codebook reordering was presented for instance by S. Sridharan and J. Leis in: “Two novel lossless algorithms to exploit index redundancy in VQ speech compression”, proceedings of ICASSP '98, pp. 57-60.
The dynamic codebook reordering approach is usually very efficient in simple one-stage quantization. When applied to advanced quantizer structures, such as multi-stage quantizers or predictive quantizers, it still brings some improvement, but the improvements are usually rather small.
When a dynamic codebook reordering is used in multistage vector quantization, the dynamic reordering technique is applied to each stage of the quantizer in isolation by evaluating the distance of the code vectors in the respective codebook to the selected code vector as the sorting criterion. This evaluation is carried out separately for each stage after storing or transmitting the codebook index at the encoder and after accessing the codebook at the decoder, to keep the synchrony between encoding and decoding. Mathematically, the sorting in stage j is done in the order of increasing distance Dj that can be computed as:Dj=d(cj,yj),  (1)where cj is the respective code vector of the codebook from stage j for which the distance is to be computed, where yj is the code vector that was just selected or retrieved from this codebook, and where d(·) is the distortion measure that is to be used. Practically any distortion measure can be applied, one example being the Euclidean distance.
The use of a dynamic codebook reordering in multistage vector quantization was described for instance by V. Krishnan, T. P. Barnwell III and D. V. Anderson in: “Using dynamic codebook re-ordering to exploit inter-frame correlation in MELP coders”, proceedings of Eurospeech/Interspeech '05, pp. 2717-2720. It was also stated in this paper that after the first stage, the code vectors are more decorrelated, which makes the reordering technique less efficient. The authors actually decided not to use the advanced multi-stage structure at all because of this reason and chose to use a simple split vector quantizer instead, despite the fact that multi-stage vector quantization clearly outperforms split vector quantization.
When a dynamic codebook reordering is used in predictive vector quantization, the dynamic codebook reordering may be realized simply by using the distance of all codebook entries to the selected codebook entry as the sorting criterion. The distance D can be computed for instance asD=d(c,y),  (2)where c is the respective code vector from the codebook for which the distance is to be computed, where y is the code vector that was just selected or retrieved from the codebook, and where d(·) is again the distortion measure. The prediction is not taken into account, except for the fact that the vectors to be quantized are prediction residuals.
Another approach for combined use of prediction and dynamic codebook reordering has been presented by F. G. B. DeNatale, S. Fioravanti and D. D. Giusto in: “DCRVQ: A new strategy for efficient entropy coding of vector-quantized images”, IEEE Transactions on Communications, vol. 44, no. 6, pp. 696-706. In this approach, the sorting criterion was:D=d(c,p),  (3)where p is the predicted vector, where c is again the particular code vector from the codebook for which the distance is computed, and where d(·) is the Euclidean distance. The actual quantization is performed straightforwardly on the input data vectors without using the prediction. With this approach, it is possible to exploit prediction, but only in a limited manner, since the code vectors are located in the original space and not in the “prediction residual” space. Thus, the prediction reduces the bitrate, but the accuracy is not improved. Moreover, this approach can only be used if the structure contains only one quantization stage.
Thus, the conventional dynamic codebook reordering techniques result only in a relatively small improvement when applied to more advanced and efficient quantization approaches, such as multi-stage vector quantization or predictive quantization.